# 31/100 链表-K个一组翻转链表
# leetcode第25题: https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked
# 本题是一个困难题, 可以先参考相关题目
# 1. g_link2_lc206 https://leetcode.cn/problems/reverse-linked-list/description/
# 2. https://leetcode.cn/problems/reverse-linked-list-ii/description/
# Date: 2024/12/27
from typing import Optional
from leetcode.bds import ListNode, ListConvert
from leetcode.test import test_function as tf


def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    def reverse(head: ListNode, tail: ListNode):
        prev = tail.next
        p = head
        while prev != tail:
            nex = p.next
            p.next = prev
            prev = p
            p = nex
        return tail, head

    hair = ListNode(0, head)
    pre = hair

    while head:
        tail = pre
        # 查看剩余部分长度是否大于等于 k
        for i in range(k):
            tail = tail.next
            if not tail:
                return ListConvert.link_to_list(hair.next)
        nex = tail.next
        head, tail = reverse(head, tail)
        # 把子链表重新接回原链表
        pre.next = head
        tail.next = nex
        pre = tail
        head = tail.next

    return ListConvert.link_to_list(hair.next)


def reverseKGroup_preprocess(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    # 统计节点个数
    n = 0
    cur = head
    while cur:
        n += 1
        cur = cur.next

    p0 = dummy = ListNode(next=head)
    pre = None
    cur = head

    # k 个一组处理
    while n >= k:
        n -= k
        for _ in range(k):  # 同 92 题
            nxt = cur.next
            cur.next = pre  # 每次循环只修改一个 next，方便大家理解
            pre = cur
            cur = nxt

        # 见视频
        nxt = p0.next
        nxt.next = cur
        p0.next = pre
        p0 = nxt
    return ListConvert.link_to_list(dummy.next)


if __name__ == '__main__':
    head1 = ListConvert.list_to_link([1, 2, 3, 4, 5])
    head2 = ListConvert.list_to_link([1, 2, 3, 4, 5])
    head3 = ListConvert.list_to_link([1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
                                      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
                                      21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33])

    inp = [{"head": head1, "k": 2}, {"head": head2, "k": 3}, {"head": head3, "k": 3}]
    out = [[2, 1, 4, 3, 5], [3, 2, 1, 4, 5],
           [3, 2, 1, 6, 5, 4, 9, 8, 7,
            12, 11, 10, 15, 14, 13, 18, 17, 16,
            21, 20, 19, 24, 23, 22, 27, 26, 25,
            30, 29, 28, 33, 32, 31]]

    tf(reverseKGroup, inp, out, times=1000)
    tf(reverseKGroup_preprocess, inp, out, times=1000)
